Giả sử phải xóa nút v trên cây AVL. Trước hết thực hiện phép xóa như với cây tìm kiếm nhị phân thông thường. Khi đó v luôn được thay bằng một nút lá hoặc nửa lá với con trái. Gọi p là cha của v, v1 là con trái của v (có thể NULL). Khi loại v khỏi cây, ta lấy con trái v1 thay vào vị trí của v. Chiều cao của cây con con gốc v1 cũng như hệ số cân bằng của nó không thay đổi, tuy nhiên chiều cao và hệ số cân bằng của nút cha p có thể thay đổi. Khi đó cũng có 4 trường hợp như khi chèn, ta chỉ việc áp dụng thủ tục REBALANCE(p).